package com.jerry.hm.algorithm.binarysearch;

/**
 * 二分查找
 *
 * @author Jerry
 * @since 2024/9/28 15:02
 */
public class BinarySearch {

    /**
     * 二分查找基础版
     *
     * @param arr    待查找的升序数组
     * @param target 待查找的目标
     * @return 找到返回索引，否则返回-1
     */
    public static int binarySearchBasic(int[] arr, int target) {
        int i = 0;
        int j = arr.length - 1;

        while (i <= j) {
            int mid = (i + j) >>> 1;
            if (target < arr[mid]) {
                j = mid - 1;
            } else if (arr[mid] < target) {
                i = mid + 1;
            } else {
                return mid;
            }
        }

        return -1;
    }

    /**
     * 二分查找改动版
     *
     * @param arr    待查找的升序数组
     * @param target 待查找的目标
     * @return 找到返回索引，否则返回-1
     */
    public static int binarySearchAlternative(int[] arr, int target) {
        int i = 0;
        int j = arr.length;

        while (i < j) {
            int mid = (i + j) >>> 1;
            if (target < arr[mid]) {
                j = mid;
            } else if (arr[mid] < target) {
                i = mid + 1;
            } else {
                return mid;
            }
        }

        return -1;
    }

    /**
     * 二分查找平衡板
     *
     * @param arr    待查找的升序数组
     * @param target 待查找的目标
     * @return 找到返回索引，否则返回-1
     */
    public static int binarySearchBalance(int[] arr, int target) {
        int i = 0;
        int j = arr.length;

        while (1 < j - i) {
            int mid = (i + j) >>> 1;
            if (target < arr[mid]) {
                j = mid;
            } else {
                i = mid;
            }
        }

        if (arr[i] == target) {
            return i;
        }

        return -1;
    }

    /**
     * 二分查找Leftmost
     *
     * @param arr    待查找的升序数组
     * @param target 待查找的目标
     * @return 找到返回索引，否则返回-1
     */
    public static int binarySearchLeftmost(int[] arr, int target) {
        int i = 0;
        int j = arr.length - 1;
        int candidate = -1;

        while (i <= j) {
            int mid = (i + j) >>> 1;
            if (target < arr[mid]) {
                j = mid - 1;
            } else if (arr[mid] < target) {
                i = mid + 1;
            } else {
                // 标记候选
                candidate = mid;
                j = mid - 1;
            }
        }

        return candidate;
    }

    /**
     * 二分查找Rightmost
     *
     * @param arr    待查找的升序数组
     * @param target 待查找的目标
     * @return 找到返回索引，否则返回-1
     */
    public static int binarySearchRightmost(int[] arr, int target) {
        int i = 0;
        int j = arr.length - 1;
        int candidate = -1;

        while (i <= j) {
            int mid = (i + j) >>> 1;
            if (target < arr[mid]) {
                j = mid - 1;
            } else if (arr[mid] < target) {
                i = mid + 1;
            } else {
                // 标记候选
                candidate = mid;
                i = mid + 1;
            }
        }

        return candidate;
    }

    /**
     * 二分查找Leftmost
     *
     * @param arr    待查找的升序数组
     * @param target 待查找的目标
     * @return 大于等于目标元素的最左索引
     */
    public static int binarySearchLeftmost2(int[] arr, int target) {
        int i = 0;
        int j = arr.length - 1;

        while (i <= j) {
            int mid = (i + j) >>> 1;
            if (target < arr[mid]) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }

        return i;
    }

    /**
     * 二分查找Rightmost
     *
     * @param arr    待查找的升序数组
     * @param target 待查找的目标
     * @return 小于等于目标元素的最右索引
     */
    public static int binarySearchRightmost2(int[] arr, int target) {
        int i = 0;
        int j = arr.length - 1;

        while (i <= j) {
            int mid = (i + j) >>> 1;
            if (target < arr[mid]) {
                j = mid - 1;
            } else {
                // 标记候选
                i = mid + 1;
            }
        }

        return i - 1;
    }
}
